import java.util.ArrayList;
import java.util.List;

public class Solution1034 {

    int[][] grid;

    boolean[][] isBean;

    int[][] directArr = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};

    List<int[]> fixLocs = new ArrayList<>();

    private boolean isInGrid(int row, int col){
        return (0 <= row && row < grid.length && 0 <= col && col < grid[0].length);
    }

    private boolean isProb(int row, int col, int targetColor){
        boolean isInGrid = isInGrid(row, col);
        if(!isInGrid || isBean[row][col] || grid[row][col] != targetColor){
            return false;
        }
        return true;
    }

    private boolean isEdge(int row, int col, int color){
        if(row == 0 || row == grid.length - 1 || col == 0 || col == grid[0].length - 1){
            return true;
        }
        for (int[] direct : directArr) {
            int tmpRow = row + direct[0];
            int tmpCol = col + direct[1];
            if(grid[tmpRow][tmpCol] != color){
                return true;
            }
        }
        return false;
    }

    private void travel(int row, int col, int color){
        if(!isProb(row, col, color)){
            return;
        }//可以经过筛选的都是在图里， 没去过， 在连通分量里的。
        isBean[row][col] = true;
        if(isEdge(row, col, color)){
            fixLocs.add(new int[]{row, col});
        }
        for (int[] direct : directArr) {
            int tmpRow = row + direct[0];
            int tmpCol = col + direct[1];
            travel(tmpRow, tmpCol, color);
        }
    }

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        this.grid = grid;
        this.isBean = new boolean[grid.length][grid[0].length];
        travel(row, col, grid[row][col]);
        for (int[] loc : fixLocs) {
            grid[loc[0]][loc[1]] = color;
        }
        return grid;
    }
}
